SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Expander code</title>

</head>

Expander code

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Expander codes</th></tr><tr><td colspan="2" class="infobox-image"><div class="infobox-caption">bipartite expander graph</div></td></tr><tr><th colspan="2" class="infobox-header" style="background:#ccf;">Classification</th></tr><tr><th scope="row" class="infobox-label">Type</th><td class="infobox-data"><a href="Linear_block_code" class="mw-redirect" title="Linear block code">Linear block code</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_block_length_n" title="Block code">Block length</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_message_length_k" title="Block code">Message length</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-m}</annotation>

</semantics>

</math><img src="./3a9677b812ea9ee4d4538767f9aef960c69aca59.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.276ex; height:2.176ex;" alt="{\displaystyle n-m}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_rate_R" title="Block code">Rate</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-m/n}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-m/n}</annotation>

</semantics>

</math><img src="./f0d5a18b361b2f272e54165a39353aa515b2501d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.6ex; height:2.843ex;" alt="{\displaystyle 1-m/n}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_distance_d" title="Block code">Distance</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2(1-\epsilon )\gamma \cdot n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2(1-\epsilon )\gamma \cdot n}</annotation>

</semantics>

</math><img src="./24971fe642059e17f618108587d93d35a19dc045.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.255ex; height:2.843ex;" alt="{\displaystyle 2(1-\epsilon )\gamma \cdot n}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_alphabet_Σ" title="Block code">Alphabet size</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#Popular_notation" title="Block code">Notation</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,n-m,2(1-\epsilon )\gamma \cdot n]_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,n-m,2(1-\epsilon )\gamma \cdot n]_{2}}</annotation>

</semantics>

</math><img src="./9d750d58c616db126e98de7b9f7f7b093b60a49b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.341ex; height:2.843ex;" alt="{\displaystyle [n,n-m,2(1-\epsilon )\gamma \cdot n]_{2}}" loading="lazy">-code</td></tr><tr><td colspan="2" class="infobox-navbar"><style data-mw-deduplicate="TemplateStyles:r1129693374">

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

In <a href="Coding_theory" title="Coding theory">coding theory</a>, expander codes form a class of <a href="Error_detection_and_correction" title="Error detection and correction">error-correcting codes</a> that are constructed from <a href="Bipartite_graph" title="Bipartite graph">bipartite</a> <a href="Expander_graph" title="Expander graph">expander graphs</a>.

Along with <a href="Justesen_code" title="Justesen code">Justesen codes</a>, expander codes are of particular interest since they have a constant positive <a href="Block_code#The_rate_R" title="Block code">rate</a>, a constant positive relative <a href="Block_code#The_distance_d" title="Block code">distance</a>, and a constant <a href="Block_code#The_alphabet_.CE.A3" title="Block code">alphabet size</a>.

In fact, the alphabet contains only two elements, so expander codes belong to the class of <a href="Binary_code" title="Binary code">binary codes</a>.

Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code.

<div class="mw-heading mw-heading2"><h2 id="Expander_codes">Expander codes</h2></div>

In <a href="Coding_theory" title="Coding theory">coding theory</a>, an expander code is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n,n-m]_{2}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n,n-m]_{2}\,}</annotation>

</semantics>

</math><img src="./3bcbaa3b1de5c4084b750ad7b5b8bf2aaac1e690.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.439ex; height:2.843ex;" alt="{\displaystyle [n,n-m]_{2}\,}" loading="lazy"> <a href="Linear_block_code" class="mw-redirect" title="Linear block code">linear block code</a> whose parity check matrix is the adjacency matrix of a bipartite <a href="Expander_graph" title="Expander graph">expander graph</a>. These codes have good relative <a href="Block_code#The_distance_d" title="Block code">distance</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2(1-\varepsilon )\gamma \,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2(1-\varepsilon )\gamma \,}</annotation>

</semantics>

</math><img src="./6a7337a771b64dded8731778b7fa02bd408d6de5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.708ex; height:2.843ex;" alt="{\displaystyle 2(1-\varepsilon )\gamma \,}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon \,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon \,}</annotation>

</semantics>

</math><img src="./137e3f3e97dfca591286d3815815dd6470bdf77b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.471ex; height:1.676ex;" alt="{\displaystyle \varepsilon \,}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma \,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma \,}</annotation>

</semantics>

</math><img src="./65da7961fee8269d576e5d06e838bf8695fc5179.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.649ex; height:2.176ex;" alt="{\displaystyle \gamma \,}" loading="lazy"> are properties of the expander graph as defined later, <a href="Block_code#The_rate_R" title="Block code">rate</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left(1-{\tfrac {m}{n}}\right)\,}">

<mrow>

<mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(1-{\tfrac {m}{n}}\right)\,}</annotation>

</semantics>

</math><img src="./fd8562dde78a548d3649430d23f8e4f9973e115b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.799ex; height:3.176ex;" alt="{\displaystyle \left(1-{\tfrac {m}{n}}\right)\,}" loading="lazy">, and decodability (algorithms of running time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)\,}</annotation>

</semantics>

</math><img src="./3554bb23e55a9844155d1713810a9f662be35b62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.364ex; height:2.843ex;" alt="{\displaystyle O(n)\,}" loading="lazy"> exist).

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> be a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (c,d)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (c,d)}</annotation>

</semantics>

</math><img src="./3ee6b94416101a5232787c5d1f20362c35adfd49.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.066ex; height:2.843ex;" alt="{\displaystyle (c,d)}" loading="lazy">-<a href="Biregular_graph" title="Biregular graph">biregular graph</a> between a set of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{v_{1},\cdots ,v_{n}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{v_{1},\cdots ,v_{n}\}}</annotation>

</semantics>

</math><img src="./add6116a438da78ec96880c126295cb34b9e605c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.031ex; height:2.843ex;" alt="{\displaystyle \{v_{1},\cdots ,v_{n}\}}" loading="lazy">, called variables, and a set of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle cn/d}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle cn/d}</annotation>

</semantics>

</math><img src="./acc2ce4a33e153444712997dc3d6d787aa957ecf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.78ex; height:2.843ex;" alt="{\displaystyle cn/d}" loading="lazy"> nodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{C_{1},\cdots ,C_{cn/d}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{C_{1},\cdots ,C_{cn/d}\}}</annotation>

</semantics>

</math><img src="./b466522e80d1fb46a90ea7e4142070dbe83add9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:15.493ex; height:3.176ex;" alt="{\displaystyle \{C_{1},\cdots ,C_{cn/d}\}}" loading="lazy">, called constraints.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b(i,j)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b(i,j)}</annotation>

</semantics>

</math><img src="./4874e434b88e0378faa8582409095df65eb4f9c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.601ex; height:2.843ex;" alt="{\displaystyle b(i,j)}" loading="lazy"> be a function designed so that, for each constraint <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}}</annotation>

</semantics>

</math><img src="./cc49dc02c0ec8c86b67e7d10518ac791eda0bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.461ex; height:2.509ex;" alt="{\displaystyle C_{i}}" loading="lazy">, the variables neighboring <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}}</annotation>

</semantics>

</math><img src="./cc49dc02c0ec8c86b67e7d10518ac791eda0bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.461ex; height:2.509ex;" alt="{\displaystyle C_{i}}" loading="lazy"> are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{b(i,1)},\cdots ,v_{b(i,d)}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{b(i,1)},\cdots ,v_{b(i,d)}}</annotation>

</semantics>

</math><img src="./aa89830c0acfaeb96450a4d8d002a3da968ff2c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:15.599ex; height:2.509ex;" alt="{\displaystyle v_{b(i,1)},\cdots ,v_{b(i,d)}}" loading="lazy">.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy"> be an error-correcting code of block length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">. The expander code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {C}}(B,{\mathcal {S}})}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}(B,{\mathcal {S}})}</annotation>

</semantics>

</math><img src="./1f8b1ca121a42fb71e425d7416b96872a5eb8048.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.339ex; height:2.843ex;" alt="{\displaystyle {\mathcal {C}}(B,{\mathcal {S}})}" loading="lazy"> is the code of block length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> whose codewords are the words <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1},\cdots ,x_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1},\cdots ,x_{n})}</annotation>

</semantics>

</math><img src="./d4c5769c108781186d381976a36b07915d7bb675.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.92ex; height:2.843ex;" alt="{\displaystyle (x_{1},\cdots ,x_{n})}" loading="lazy"> such that, for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq cn/d}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq cn/d}</annotation>

</semantics>

</math><img src="./6f2e6a2c71c7cab75397cdfa78997e6069c89ddf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.942ex; height:2.843ex;" alt="{\displaystyle 1\leq i\leq cn/d}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{b(i,1)},\cdots ,x_{b(i,d)})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{b(i,1)},\cdots ,x_{b(i,d)})}</annotation>

</semantics>

</math><img src="./1d00f8b19c2c9abf4fe2a6984a43ee33e52f8bd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:17.812ex; height:3.176ex;" alt="{\displaystyle (x_{b(i,1)},\cdots ,x_{b(i,d)})}" loading="lazy"> is a codeword of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {S}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {S}}}</annotation>

</semantics>

</math><img src="./2302a18e269dbecc43c57c0c2aced3bfae15278d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.492ex; height:2.176ex;" alt="{\displaystyle {\mathcal {S}}}" loading="lazy">.<a href="#cite_note-definition-1">[1]</a>

It has been shown that nontrivial lossless expander graphs exist. Moreover, we can explicitly construct them.<a href="#cite_note-lossless-2">[2]</a>

The rate of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\,}</annotation>

</semantics>

</math><img src="./785a192e3331793e37b1be0c5315d196da1a7049.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.153ex; height:2.176ex;" alt="{\displaystyle C\,}" loading="lazy"> is its dimension divided by its block length. In this case, the parity check matrix has size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\times n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\times n\,}</annotation>

</semantics>

</math><img src="./b00421d407ffb82eea36d742ee3e08a5e2e1cddb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.663ex; height:1.676ex;" alt="{\displaystyle m\times n\,}" loading="lazy">, and hence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\,}</annotation>

</semantics>

</math><img src="./785a192e3331793e37b1be0c5315d196da1a7049.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.153ex; height:2.176ex;" alt="{\displaystyle C\,}" loading="lazy"> has rate at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n-m)/n=1-m/n\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n-m)/n=1-m/n\,}</annotation>

</semantics>

</math><img src="./d1512aaac4af80b363307261a4718a8d7670ce9e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.728ex; height:2.843ex;" alt="{\displaystyle (n-m)/n=1-m/n\,}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Distance">Distance</h2></div>

Suppose <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}</annotation>

</semantics>

</math><img src="./ca27cc3bd23bfaf2f1b5e160d8c2837dba473e5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:6.227ex; height:3.509ex;" alt="{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}" loading="lazy">. Then the distance of a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,m,d,\gamma ,1-\varepsilon )\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,m,d,\gamma ,1-\varepsilon )\,}</annotation>

</semantics>

</math><img src="./0a721dd8ee207d376e1f751f2874a1429735a697.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.332ex; height:2.843ex;" alt="{\displaystyle (n,m,d,\gamma ,1-\varepsilon )\,}" loading="lazy"> expander code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\,}</annotation>

</semantics>

</math><img src="./785a192e3331793e37b1be0c5315d196da1a7049.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.153ex; height:2.176ex;" alt="{\displaystyle C\,}" loading="lazy"> is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2(1-\varepsilon )\gamma n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2(1-\varepsilon )\gamma n\,}</annotation>

</semantics>

</math><img src="./1b9033fd6883aeab4dbf897075038a76c2fb492d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.102ex; height:2.843ex;" alt="{\displaystyle 2(1-\varepsilon )\gamma n\,}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Proof">Proof</h3></div>

Note that we can consider every codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\,}</annotation>

</semantics>

</math><img src="./8573e7d95140b0d4068258d8162e189563baee6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.394ex; height:1.676ex;" alt="{\displaystyle c\,}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\,}</annotation>

</semantics>

</math><img src="./785a192e3331793e37b1be0c5315d196da1a7049.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.153ex; height:2.176ex;" alt="{\displaystyle C\,}" loading="lazy"> as a subset of vertices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subset L\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\subset L\,}</annotation>

</semantics>

</math><img src="./5767c70723a619b005e5befcd52908964475e7fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.568ex; height:2.176ex;" alt="{\displaystyle S\subset L\,}" loading="lazy">, by saying that vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}\in S\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}\in S\,}</annotation>

</semantics>

</math><img src="./a2e312c322adfbcc64eacab130f2bac250a01fd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.654ex; height:2.509ex;" alt="{\displaystyle v_{i}\in S\,}" loading="lazy"> if and only if the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\,}</annotation>

</semantics>

</math><img src="./a8288705aba0c3da0eae22f3895f572ecc2ccdf8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.19ex; height:2.176ex;" alt="{\displaystyle i\,}" loading="lazy">th index of the codeword is a 1. Then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\,}</annotation>

</semantics>

</math><img src="./8573e7d95140b0d4068258d8162e189563baee6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.394ex; height:1.676ex;" alt="{\displaystyle c\,}" loading="lazy"> is a codeword iff every vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in R\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in R\,}</annotation>

</semantics>

</math><img src="./438b20c278b9ccc6a74747649ef20e40ac5a29c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.119ex; height:2.176ex;" alt="{\displaystyle v\in R\,}" loading="lazy"> is adjacent to an even number of vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\,}</annotation>

</semantics>

</math><img src="./933054f2b86e79da95030b113a7c7dfdff643268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.886ex; height:2.176ex;" alt="{\displaystyle S\,}" loading="lazy">. (In order to be a codeword, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle cP=0\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle cP=0\,}</annotation>

</semantics>

</math><img src="./139d297c8d5b72fcc21ee89c032b52d66b428fa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.4ex; height:2.176ex;" alt="{\displaystyle cP=0\,}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P\,}</annotation>

</semantics>

</math><img src="./f60e07ebc2aadee94e4cbbccef71fd9bcf44f5f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.133ex; height:2.176ex;" alt="{\displaystyle P\,}" loading="lazy"> is the parity check matrix. Then, each vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\,}</annotation>

</semantics>

</math><img src="./293563891196765d2d51e0dd54e1ae1000ba9def.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.151ex; height:2.176ex;" alt="{\displaystyle R\,}" loading="lazy"> corresponds to each column of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P\,}</annotation>

</semantics>

</math><img src="./f60e07ebc2aadee94e4cbbccef71fd9bcf44f5f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.133ex; height:2.176ex;" alt="{\displaystyle P\,}" loading="lazy">. Matrix multiplication over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{GF}}(2)=\{0,1\}\,}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{GF}}(2)=\{0,1\}\,}</annotation>

</semantics>

</math><img src="./d363caeb9e74941e57f2685dfb15b11deee19900.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.483ex; height:2.843ex;" alt="{\displaystyle {\text{GF}}(2)=\{0,1\}\,}" loading="lazy"> then gives the desired result.) So, if a vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in R\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in R\,}</annotation>

</semantics>

</math><img src="./438b20c278b9ccc6a74747649ef20e40ac5a29c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.119ex; height:2.176ex;" alt="{\displaystyle v\in R\,}" loading="lazy"> is adjacent to a single vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\,}</annotation>

</semantics>

</math><img src="./933054f2b86e79da95030b113a7c7dfdff643268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.886ex; height:2.176ex;" alt="{\displaystyle S\,}" loading="lazy">, we know immediately that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\,}</annotation>

</semantics>

</math><img src="./8573e7d95140b0d4068258d8162e189563baee6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.394ex; height:1.676ex;" alt="{\displaystyle c\,}" loading="lazy"> is not a codeword. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N(S)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N(S)\,}</annotation>

</semantics>

</math><img src="./31dbc2e1695a9c711174a0bed953cbac77b102ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.759ex; height:2.843ex;" alt="{\displaystyle N(S)\,}" loading="lazy"> denote the neighbors in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\,}</annotation>

</semantics>

</math><img src="./293563891196765d2d51e0dd54e1ae1000ba9def.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.151ex; height:2.176ex;" alt="{\displaystyle R\,}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\,}</annotation>

</semantics>

</math><img src="./933054f2b86e79da95030b113a7c7dfdff643268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.886ex; height:2.176ex;" alt="{\displaystyle S\,}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U(S)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U(S)\,}</annotation>

</semantics>

</math><img src="./d05e958209b042e09eae495b4a9fb8a04de5bf7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.478ex; height:2.843ex;" alt="{\displaystyle U(S)\,}" loading="lazy"> denote those neighbors of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\,}</annotation>

</semantics>

</math><img src="./933054f2b86e79da95030b113a7c7dfdff643268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.886ex; height:2.176ex;" alt="{\displaystyle S\,}" loading="lazy"> which are unique, i.e., adjacent to a single vertex of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\,}</annotation>

</semantics>

</math><img src="./933054f2b86e79da95030b113a7c7dfdff643268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.886ex; height:2.176ex;" alt="{\displaystyle S\,}" loading="lazy">.

<div class="mw-heading mw-heading4"><h4 id="Lemma_1">Lemma 1</h4></div>

For every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subset L\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\subset L\,}</annotation>

</semantics>

</math><img src="./5767c70723a619b005e5befcd52908964475e7fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.568ex; height:2.176ex;" alt="{\displaystyle S\subset L\,}" loading="lazy"> of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |S|\leq \gamma n\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |S|\leq \gamma n\,}</annotation>

</semantics>

</math><img src="./9e57e362761559816d16d6d3aeb329f87a0c901e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.936ex; height:2.843ex;" alt="{\displaystyle |S|\leq \gamma n\,}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d|S|\geq |N(S)|\geq |U(S)|\geq d(1-2\varepsilon )|S|\,}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d|S|\geq |N(S)|\geq |U(S)|\geq d(1-2\varepsilon )|S|\,}</annotation>

</semantics>

</math><img src="./eebcadfbd8724b4d3e69fea1f70de89d8613b7ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:38.809ex; height:2.843ex;" alt="{\displaystyle d|S|\geq |N(S)|\geq |U(S)|\geq d(1-2\varepsilon )|S|\,}" loading="lazy">.

<div class="mw-heading mw-heading4"><h4 id="Proof_2">Proof</h4></div>

Trivially, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |N(S)|\geq |U(S)|\,}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |N(S)|\geq |U(S)|\,}</annotation>

</semantics>

</math><img src="./2744bf246c74b14de4807c35074cc723e7e4b7ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.536ex; height:2.843ex;" alt="{\displaystyle |N(S)|\geq |U(S)|\,}" loading="lazy">, since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in U(S)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in U(S)\,}</annotation>

</semantics>

</math><img src="./172594492f4218dbcf0a50098f1fc85ac848b7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.446ex; height:2.843ex;" alt="{\displaystyle v\in U(S)\,}" loading="lazy"> implies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in N(S)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in N(S)\,}</annotation>

</semantics>

</math><img src="./1b682c602da47aefbbd395455e156ed87c7e3c75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.728ex; height:2.843ex;" alt="{\displaystyle v\in N(S)\,}" loading="lazy">. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |N(S)|\leq d|S|\,}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |N(S)|\leq d|S|\,}</annotation>

</semantics>

</math><img src="./69599da321a354efb20eba2d9578d9787803fe5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.16ex; height:2.843ex;" alt="{\displaystyle |N(S)|\leq d|S|\,}" loading="lazy"> follows since the degree of every vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\,}</annotation>

</semantics>

</math><img src="./933054f2b86e79da95030b113a7c7dfdff643268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.886ex; height:2.176ex;" alt="{\displaystyle S\,}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\,}</annotation>

</semantics>

</math><img src="./0f203b686a923982358b9274fb508753ac31b996.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.603ex; height:2.176ex;" alt="{\displaystyle d\,}" loading="lazy">. By the expansion property of the graph, there must be a set of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d(1-\varepsilon )|S|\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(1-\varepsilon )|S|\,}</annotation>

</semantics>

</math><img src="./cc27d2889ac0797aa659d1c289ff29e843e5a674.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.292ex; height:2.843ex;" alt="{\displaystyle d(1-\varepsilon )|S|\,}" loading="lazy"> edges which go to distinct vertices. The remaining <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\varepsilon |S|\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\varepsilon |S|\,}</annotation>

</semantics>

</math><img src="./46a1f600ad2e02ff306fc45da24ab5de0ea6cde4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.479ex; height:2.843ex;" alt="{\displaystyle d\varepsilon |S|\,}" loading="lazy"> edges make at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\varepsilon |S|\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\varepsilon |S|\,}</annotation>

</semantics>

</math><img src="./46a1f600ad2e02ff306fc45da24ab5de0ea6cde4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.479ex; height:2.843ex;" alt="{\displaystyle d\varepsilon |S|\,}" loading="lazy"> neighbors not unique, so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U(S)\geq d(1-\varepsilon )|S|-d\varepsilon |S|=d(1-2\varepsilon )|S|\,}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U(S)\geq d(1-\varepsilon )|S|-d\varepsilon |S|=d(1-2\varepsilon )|S|\,}</annotation>

</semantics>

</math><img src="./de749795a9bd420bfa45c24eb732f4d0dc0d93e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.579ex; height:2.843ex;" alt="{\displaystyle U(S)\geq d(1-\varepsilon )|S|-d\varepsilon |S|=d(1-2\varepsilon )|S|\,}" loading="lazy">.

<div class="mw-heading mw-heading4"><h4 id="Corollary">Corollary</h4></div>

Every sufficiently small <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\,}</annotation>

</semantics>

</math><img src="./933054f2b86e79da95030b113a7c7dfdff643268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.886ex; height:2.176ex;" alt="{\displaystyle S\,}" loading="lazy"> has a unique neighbor. This follows since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}</annotation>

</semantics>

</math><img src="./ca27cc3bd23bfaf2f1b5e160d8c2837dba473e5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:6.227ex; height:3.509ex;" alt="{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}" loading="lazy">.

<div class="mw-heading mw-heading4"><h4 id="Lemma_2">Lemma 2</h4></div>

Every subset <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\subset L\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\subset L\,}</annotation>

</semantics>

</math><img src="./e628788714f0d0149649e6a11ca21936248e2d86.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.705ex; height:2.176ex;" alt="{\displaystyle T\subset L\,}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |T|<2(1-\varepsilon )\gamma n\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |T|<2(1-\varepsilon )\gamma n\,}</annotation>

</semantics>

</math><img src="./759bb4173501e604e37051074e0aeb88012ec6f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.131ex; height:2.843ex;" alt="{\displaystyle |T|<2(1-\varepsilon )\gamma n\,}" loading="lazy"> has a unique neighbor.

<div class="mw-heading mw-heading4"><h4 id="Proof_3">Proof</h4></div>

Lemma 1 proves the case <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |T|\leq \gamma n\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |T|\leq \gamma n\,}</annotation>

</semantics>

</math><img src="./93d32410ceec19cefa551973a460bbc79212293b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.073ex; height:2.843ex;" alt="{\displaystyle |T|\leq \gamma n\,}" loading="lazy">, so suppose <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2(1-\varepsilon )\gamma n>|T|>\gamma n\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2(1-\varepsilon )\gamma n>|T|>\gamma n\,}</annotation>

</semantics>

</math><img src="./0b0a97112c6a3207dce9159bb9e62ad2b1ca9de3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.886ex; height:2.843ex;" alt="{\displaystyle 2(1-\varepsilon )\gamma n>|T|>\gamma n\,}" loading="lazy">. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subset T\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\subset T\,}</annotation>

</semantics>

</math><img src="./be62969c25d7744423b1cbc1793a0042f82f8e1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.621ex; height:2.176ex;" alt="{\displaystyle S\subset T\,}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |S|=\gamma n\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |S|=\gamma n\,}</annotation>

</semantics>

</math><img src="./7b71b77eba32df75953fc24098d13f8da5bc4ae8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.936ex; height:2.843ex;" alt="{\displaystyle |S|=\gamma n\,}" loading="lazy">. By Lemma 1, we know that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |U(S)|\geq d(1-2\varepsilon )|S|\,}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |U(S)|\geq d(1-2\varepsilon )|S|\,}</annotation>

</semantics>

</math><img src="./6a1c3680380a595d500abc6f65426932e80944f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.937ex; height:2.843ex;" alt="{\displaystyle |U(S)|\geq d(1-2\varepsilon )|S|\,}" loading="lazy">. Then a vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\in U(S)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\in U(S)\,}</annotation>

</semantics>

</math><img src="./172594492f4218dbcf0a50098f1fc85ac848b7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.446ex; height:2.843ex;" alt="{\displaystyle v\in U(S)\,}" loading="lazy"> is in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U(T)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U(T)\,}</annotation>

</semantics>

</math><img src="./7b9020d48c0d01dd7e68b2edbd86d5a84edd5b94.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.615ex; height:2.843ex;" alt="{\displaystyle U(T)\,}" loading="lazy"> iff <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v\notin N(T\setminus S)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v\notin N(T\setminus S)\,}</annotation>

</semantics>

</math><img src="./94c8f81b4d569c76e07910c45068967e30c40cf3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.559ex; height:2.843ex;" alt="{\displaystyle v\notin N(T\setminus S)\,}" loading="lazy">, and we know that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |T\setminus S|\leq 2(1-\varepsilon )\gamma n-\gamma n=(1-2\varepsilon )\gamma n\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |T\setminus S|\leq 2(1-\varepsilon )\gamma n-\gamma n=(1-2\varepsilon )\gamma n\,}</annotation>

</semantics>

</math><img src="./e2f327cb1205c1e60800cbff5d6df2dbe0bde3f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.136ex; height:2.843ex;" alt="{\displaystyle |T\setminus S|\leq 2(1-\varepsilon )\gamma n-\gamma n=(1-2\varepsilon )\gamma n\,}" loading="lazy">, so by the first part of Lemma 1, we know <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |N(T\setminus S)|\leq d(1-2\varepsilon )\gamma n\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |N(T\setminus S)|\leq d(1-2\varepsilon )\gamma n\,}</annotation>

</semantics>

</math><img src="./8d0e82185bb47dc1bb6dd5653f608f986f87ef3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.913ex; height:2.843ex;" alt="{\displaystyle |N(T\setminus S)|\leq d(1-2\varepsilon )\gamma n\,}" loading="lazy">. Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}</annotation>

</semantics>

</math><img src="./ca27cc3bd23bfaf2f1b5e160d8c2837dba473e5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:6.227ex; height:3.509ex;" alt="{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |U(T)|\geq |U(S)\setminus N(T\setminus S)|\geq |U(S)|-|N(T\setminus S)|>0\,}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |U(T)|\geq |U(S)\setminus N(T\setminus S)|\geq |U(S)|-|N(T\setminus S)|>0\,}</annotation>

</semantics>

</math><img src="./4ba29433eaff8d16c1424093c18a707d0c14ac2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:54.871ex; height:2.843ex;" alt="{\displaystyle |U(T)|\geq |U(S)\setminus N(T\setminus S)|\geq |U(S)|-|N(T\setminus S)|>0\,}" loading="lazy">, and hence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U(T)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U(T)\,}</annotation>

</semantics>

</math><img src="./7b9020d48c0d01dd7e68b2edbd86d5a84edd5b94.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.615ex; height:2.843ex;" alt="{\displaystyle U(T)\,}" loading="lazy"> is not empty.

<div class="mw-heading mw-heading4"><h4 id="Corollary_2">Corollary</h4></div>

Note that if a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\subset L\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\subset L\,}</annotation>

</semantics>

</math><img src="./e628788714f0d0149649e6a11ca21936248e2d86.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.705ex; height:2.176ex;" alt="{\displaystyle T\subset L\,}" loading="lazy"> has at least 1 unique neighbor, i.e. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |U(T)|>0\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |U(T)|>0\,}</annotation>

</semantics>

</math><img src="./d15e5d4f56af8a7bca8094d1c150c2efaafd362c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.17ex; height:2.843ex;" alt="{\displaystyle |U(T)|>0\,}" loading="lazy">, then the corresponding word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\,}</annotation>

</semantics>

</math><img src="./8573e7d95140b0d4068258d8162e189563baee6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.394ex; height:1.676ex;" alt="{\displaystyle c\,}" loading="lazy"> corresponding to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\,}</annotation>

</semantics>

</math><img src="./476a8389064c06ab89963a2467aef525838da0cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.023ex; height:2.176ex;" alt="{\displaystyle T\,}" loading="lazy"> cannot be a codeword, as it will not multiply to the all zeros vector by the parity check matrix. By the previous argument, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\in C\implies wt(c)\geq 2(1-\varepsilon )\gamma n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\in C\implies wt(c)\geq 2(1-\varepsilon )\gamma n\,}</annotation>

</semantics>

</math><img src="./d75b6355e44ea19f1114d02255e9524c314e975f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.521ex; height:2.843ex;" alt="{\displaystyle c\in C\implies wt(c)\geq 2(1-\varepsilon )\gamma n\,}" loading="lazy">. Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\,}</annotation>

</semantics>

</math><img src="./785a192e3331793e37b1be0c5315d196da1a7049.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.153ex; height:2.176ex;" alt="{\displaystyle C\,}" loading="lazy"> is linear, we conclude that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\,}</annotation>

</semantics>

</math><img src="./785a192e3331793e37b1be0c5315d196da1a7049.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.153ex; height:2.176ex;" alt="{\displaystyle C\,}" loading="lazy"> has distance at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2(1-\varepsilon )\gamma n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2(1-\varepsilon )\gamma n\,}</annotation>

</semantics>

</math><img src="./1b9033fd6883aeab4dbf897075038a76c2fb492d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.102ex; height:2.843ex;" alt="{\displaystyle 2(1-\varepsilon )\gamma n\,}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Encoding">Encoding</h2></div>

The encoding time for an expander code is upper bounded by that of a general linear code - <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})\,}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})\,}</annotation>

</semantics>

</math><img src="./c4bf592ad47e6d7debb8965443b0aa8ff75c85cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.419ex; height:3.176ex;" alt="{\displaystyle O(n^{2})\,}" loading="lazy"> by matrix multiplication. A result due to Spielman shows that encoding is possible in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)\,}</annotation>

</semantics>

</math><img src="./3554bb23e55a9844155d1713810a9f662be35b62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.364ex; height:2.843ex;" alt="{\displaystyle O(n)\,}" loading="lazy"> time.<a href="#cite_note-spielman-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Decoding">Decoding</h2></div>

Decoding of expander codes is possible in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n)\,}</annotation>

</semantics>

</math><img src="./3554bb23e55a9844155d1713810a9f662be35b62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.364ex; height:2.843ex;" alt="{\displaystyle O(n)\,}" loading="lazy"> time when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon <{\tfrac {1}{4}}\,}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon <{\tfrac {1}{4}}\,}</annotation>

</semantics>

</math><img src="./55d3f36e8d3dd216f448731af1759b947972db94.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:6.227ex; height:3.509ex;" alt="{\displaystyle \varepsilon <{\tfrac {1}{4}}\,}" loading="lazy"> using the following algorithm.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}\,}</annotation>

</semantics>

</math><img src="./e553751e245e05abb36ab6cff54f86b0037b759c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.314ex; height:2.009ex;" alt="{\displaystyle v_{i}\,}" loading="lazy"> be the vertex of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L\,}</annotation>

</semantics>

</math><img src="./d330bc0cd693cc87e3943137dc591038a89f77e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.97ex; height:2.176ex;" alt="{\displaystyle L\,}" loading="lazy"> that corresponds to the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\,}</annotation>

</semantics>

</math><img src="./a8288705aba0c3da0eae22f3895f572ecc2ccdf8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.19ex; height:2.176ex;" alt="{\displaystyle i\,}" loading="lazy">th index in the codewords of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\,}</annotation>

</semantics>

</math><img src="./785a192e3331793e37b1be0c5315d196da1a7049.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.153ex; height:2.176ex;" alt="{\displaystyle C\,}" loading="lazy">. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in \{0,1\}^{n}\,}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in \{0,1\}^{n}\,}</annotation>

</semantics>

</math><img src="./7b8447adc8880413153fbc4945f65944a3645402.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.285ex; height:2.843ex;" alt="{\displaystyle y\in \{0,1\}^{n}\,}" loading="lazy"> be a received word, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V(y)=\{v_{i}\mid {\text{the }}i^{\text{th}}{\text{ position of }}y{\text{ is a }}1\}\,}">

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

<mtext> position of </mtext>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V(y)=\{v_{i}\mid {\text{the }}i^{\text{th}}{\text{ position of }}y{\text{ is a }}1\}\,}</annotation>

</semantics>

</math><img src="./820b28875b792d78062efea8a55e55d626633f83.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:39.252ex; height:3.176ex;" alt="{\displaystyle V(y)=\{v_{i}\mid {\text{the }}i^{\text{th}}{\text{ position of }}y{\text{ is a }}1\}\,}" loading="lazy">. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e(i)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e(i)\,}</annotation>

</semantics>

</math><img src="./efff257f1faf44a519af9add3e4f9f31c63db10c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.082ex; height:2.843ex;" alt="{\displaystyle e(i)\,}" loading="lazy"> be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is even}}\}|\,}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is even}}\}|\,}</annotation>

</semantics>

</math><img src="./17da87971983a36ce9060a7d4ea8f7556080df19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.997ex; height:2.843ex;" alt="{\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is even}}\}|\,}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o(i)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o(i)\,}</annotation>

</semantics>

</math><img src="./2e740f3d37d465f784bde17206ed33faea1e3c4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.126ex; height:2.843ex;" alt="{\displaystyle o(i)\,}" loading="lazy"> be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is odd}}\}|\,}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is odd}}\}|\,}</annotation>

</semantics>

</math><img src="./62767baa1ac22e9db9632da0feebac48e4d42421.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.159ex; height:2.843ex;" alt="{\displaystyle |\{v\in R\mid v_{i}\in N(v){\text{ and }}N(v)\cap V(y){\text{ is odd}}\}|\,}" loading="lazy">. Then consider the greedy algorithm:

<hr>

Input: received word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\,}</annotation>

</semantics>

</math><img src="./1c8c233e7cc39fac816991250d86e09b515d02e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.543ex; height:2.009ex;" alt="{\displaystyle y\,}" loading="lazy">.

<pre>initialize y' to y

while there is a v in R adjacent to an odd number of vertices in V(y')

if there is an i such that o(i) > e(i)

flip entry i in y'

else

fail

</pre>

Output: fail, or modified codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y'\,}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y'\,}</annotation>

</semantics>

</math><img src="./1958140310e24d37de4b685938f2921245a1c147.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.232ex; height:2.843ex;" alt="{\displaystyle y'\,}" loading="lazy">.

<hr>

<div class="mw-heading mw-heading3"><h3 id="Proof_4">Proof</h3></div>

We show first the correctness of the algorithm, and then examine its running time.

<div class="mw-heading mw-heading4"><h4 id="Correctness">Correctness</h4></div>

We must show that the algorithm terminates with the correct codeword when the received codeword is within half the code's distance of the original codeword. Let the set of corrupt variables be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\,}</annotation>

</semantics>

</math><img src="./933054f2b86e79da95030b113a7c7dfdff643268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.886ex; height:2.176ex;" alt="{\displaystyle S\,}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=|S|\,}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=|S|\,}</annotation>

</semantics>

</math><img src="./b564b04888cf23d8871a7013149e6dda4a8bf68f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.369ex; height:2.843ex;" alt="{\displaystyle s=|S|\,}" loading="lazy">, and the set of unsatisfied (adjacent to an odd number of vertices) vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\,}</annotation>

</semantics>

</math><img src="./293563891196765d2d51e0dd54e1ae1000ba9def.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.151ex; height:2.176ex;" alt="{\displaystyle R\,}" loading="lazy"> be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\,}</annotation>

</semantics>

</math><img src="./8573e7d95140b0d4068258d8162e189563baee6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.394ex; height:1.676ex;" alt="{\displaystyle c\,}" loading="lazy">. The following lemma will prove useful.

<div class="mw-heading mw-heading5"><h5 id="Lemma_3">Lemma 3</h5></div>

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0<s<\gamma n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0<s<\gamma n\,}</annotation>

</semantics>

</math><img src="./effa1af345de57d06be1c30b7316b5ea9e71615b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.494ex; height:2.676ex;" alt="{\displaystyle 0<s<\gamma n\,}" loading="lazy">, then there is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}\,}</annotation>

</semantics>

</math><img src="./e553751e245e05abb36ab6cff54f86b0037b759c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.314ex; height:2.009ex;" alt="{\displaystyle v_{i}\,}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o(i)>e(i)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o(i)>e(i)\,}</annotation>

</semantics>

</math><img src="./5a5074fcff782572239cabd11c746217440a20bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.92ex; height:2.843ex;" alt="{\displaystyle o(i)>e(i)\,}" loading="lazy">.

<div class="mw-heading mw-heading5"><h5 id="Proof_5">Proof</h5></div>

By Lemma 1, we know that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U(S)\geq d(1-2\varepsilon )s\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U(S)\geq d(1-2\varepsilon )s\,}</annotation>

</semantics>

</math><img src="./fd4eddc3bc804bd59593ef8bdff97622d42a24fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.941ex; height:2.843ex;" alt="{\displaystyle U(S)\geq d(1-2\varepsilon )s\,}" loading="lazy">. So an average vertex has at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d(1-2\varepsilon )>d/2\,}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(1-2\varepsilon )>d/2\,}</annotation>

</semantics>

</math><img src="./7b9928818d18393d5c8f93972d7d8d3caea30538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.3ex; height:2.843ex;" alt="{\displaystyle d(1-2\varepsilon )>d/2\,}" loading="lazy"> unique neighbors (recall unique neighbors are unsatisfied and hence contribute to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o(i)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o(i)\,}</annotation>

</semantics>

</math><img src="./2e740f3d37d465f784bde17206ed33faea1e3c4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.126ex; height:2.843ex;" alt="{\displaystyle o(i)\,}" loading="lazy">), since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon <{\tfrac {1}{4}}\,}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon <{\tfrac {1}{4}}\,}</annotation>

</semantics>

</math><img src="./55d3f36e8d3dd216f448731af1759b947972db94.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:6.227ex; height:3.509ex;" alt="{\displaystyle \varepsilon <{\tfrac {1}{4}}\,}" loading="lazy">, and thus there is a vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}\,}</annotation>

</semantics>

</math><img src="./e553751e245e05abb36ab6cff54f86b0037b759c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.314ex; height:2.009ex;" alt="{\displaystyle v_{i}\,}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o(i)>e(i)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o(i)>e(i)\,}</annotation>

</semantics>

</math><img src="./5a5074fcff782572239cabd11c746217440a20bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.92ex; height:2.843ex;" alt="{\displaystyle o(i)>e(i)\,}" loading="lazy">.

So, if we have not yet reached a codeword, then there will always be some vertex to flip. Next, we show that the number of errors can never increase beyond <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma n\,}</annotation>

</semantics>

</math><img src="./8ead72c5d7e33ed891812d7d749bd47c52e5cafa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.044ex; height:2.176ex;" alt="{\displaystyle \gamma n\,}" loading="lazy">.

<div class="mw-heading mw-heading5"><h5 id="Lemma_4">Lemma 4</h5></div>

If we start with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s<\gamma (1-2\varepsilon )n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s<\gamma (1-2\varepsilon )n\,}</annotation>

</semantics>

</math><img src="./eb253faab5f4fb1030e5a8bf737da8c7a09ca37b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.291ex; height:2.843ex;" alt="{\displaystyle s<\gamma (1-2\varepsilon )n\,}" loading="lazy">, then we never reach <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s=\gamma n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s=\gamma n\,}</annotation>

</semantics>

</math><img src="./26e25dd58ab0a0aa850d8b308774962044c5368e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.233ex; height:2.176ex;" alt="{\displaystyle s=\gamma n\,}" loading="lazy"> at any point in the algorithm.

<div class="mw-heading mw-heading5"><h5 id="Proof_6">Proof</h5></div>

When we flip a vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}\,}</annotation>

</semantics>

</math><img src="./e553751e245e05abb36ab6cff54f86b0037b759c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.314ex; height:2.009ex;" alt="{\displaystyle v_{i}\,}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o(i)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o(i)\,}</annotation>

</semantics>

</math><img src="./2e740f3d37d465f784bde17206ed33faea1e3c4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.126ex; height:2.843ex;" alt="{\displaystyle o(i)\,}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e(i)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e(i)\,}</annotation>

</semantics>

</math><img src="./efff257f1faf44a519af9add3e4f9f31c63db10c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.082ex; height:2.843ex;" alt="{\displaystyle e(i)\,}" loading="lazy"> are interchanged, and since we had <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o(i)>e(i)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o(i)>e(i)\,}</annotation>

</semantics>

</math><img src="./5a5074fcff782572239cabd11c746217440a20bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.92ex; height:2.843ex;" alt="{\displaystyle o(i)>e(i)\,}" loading="lazy">, this means the number of unsatisfied vertices on the right decreases by at least one after each flip. Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s<\gamma (1-2\varepsilon )n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s<\gamma (1-2\varepsilon )n\,}</annotation>

</semantics>

</math><img src="./eb253faab5f4fb1030e5a8bf737da8c7a09ca37b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.291ex; height:2.843ex;" alt="{\displaystyle s<\gamma (1-2\varepsilon )n\,}" loading="lazy">, the initial number of unsatisfied vertices is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\gamma (1-2\varepsilon )n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\gamma (1-2\varepsilon )n\,}</annotation>

</semantics>

</math><img src="./b102ba651de911339f2faf7671a609b44c562592.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.318ex; height:2.843ex;" alt="{\displaystyle d\gamma (1-2\varepsilon )n\,}" loading="lazy">, by the graph's <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\,}</annotation>

</semantics>

</math><img src="./0f203b686a923982358b9274fb508753ac31b996.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.603ex; height:2.176ex;" alt="{\displaystyle d\,}" loading="lazy">-regularity. If we reached a string with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma n\,}</annotation>

</semantics>

</math><img src="./8ead72c5d7e33ed891812d7d749bd47c52e5cafa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.044ex; height:2.176ex;" alt="{\displaystyle \gamma n\,}" loading="lazy"> errors, then by Lemma 1, there would be at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\gamma (1-2\varepsilon )n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\gamma (1-2\varepsilon )n\,}</annotation>

</semantics>

</math><img src="./b102ba651de911339f2faf7671a609b44c562592.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.318ex; height:2.843ex;" alt="{\displaystyle d\gamma (1-2\varepsilon )n\,}" loading="lazy"> unique neighbors, which means there would be at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\gamma (1-2\varepsilon )n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\gamma (1-2\varepsilon )n\,}</annotation>

</semantics>

</math><img src="./b102ba651de911339f2faf7671a609b44c562592.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.318ex; height:2.843ex;" alt="{\displaystyle d\gamma (1-2\varepsilon )n\,}" loading="lazy"> unsatisfied vertices, a contradiction.

Lemmas 3 and 4 show us that if we start with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s<\gamma (1-2\varepsilon )n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s<\gamma (1-2\varepsilon )n\,}</annotation>

</semantics>

</math><img src="./eb253faab5f4fb1030e5a8bf737da8c7a09ca37b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.291ex; height:2.843ex;" alt="{\displaystyle s<\gamma (1-2\varepsilon )n\,}" loading="lazy"> (half the distance of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\,}</annotation>

</semantics>

</math><img src="./785a192e3331793e37b1be0c5315d196da1a7049.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.153ex; height:2.176ex;" alt="{\displaystyle C\,}" loading="lazy">), then we will always find a vertex <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}\,}</annotation>

</semantics>

</math><img src="./e553751e245e05abb36ab6cff54f86b0037b759c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.314ex; height:2.009ex;" alt="{\displaystyle v_{i}\,}" loading="lazy"> to flip. Each flip reduces the number of unsatisfied vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\,}</annotation>

</semantics>

</math><img src="./293563891196765d2d51e0dd54e1ae1000ba9def.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.151ex; height:2.176ex;" alt="{\displaystyle R\,}" loading="lazy"> by at least 1, and hence the algorithm terminates in at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\,}</annotation>

</semantics>

</math><img src="./37129e832c2c81b9f146dd22228d409bd099b295.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.427ex; height:1.676ex;" alt="{\displaystyle m\,}" loading="lazy"> steps, and it terminates at some codeword, by Lemma 3. (Were it not at a codeword, there would be some vertex to flip). Lemma 4 shows us that we can never be farther than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma n\,}</annotation>

</semantics>

</math><img src="./8ead72c5d7e33ed891812d7d749bd47c52e5cafa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.044ex; height:2.176ex;" alt="{\displaystyle \gamma n\,}" loading="lazy"> away from the correct codeword. Since the code has distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2(1-\varepsilon )\gamma n>\gamma n\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2(1-\varepsilon )\gamma n>\gamma n\,}</annotation>

</semantics>

</math><img src="./101f601e04f055686d7af7664a4af56e9549521b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.858ex; height:2.843ex;" alt="{\displaystyle 2(1-\varepsilon )\gamma n>\gamma n\,}" loading="lazy"> (since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}</annotation>

</semantics>

</math><img src="./ca27cc3bd23bfaf2f1b5e160d8c2837dba473e5c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:6.227ex; height:3.509ex;" alt="{\displaystyle \varepsilon <{\tfrac {1}{2}}\,}" loading="lazy">), the codeword it terminates on must be the correct codeword, since the number of bit flips is less than half the distance (so we couldn't have traveled far enough to reach any other codeword).

<div class="mw-heading mw-heading4"><h4 id="Complexity">Complexity</h4></div>

We now show that the algorithm can achieve linear time decoding. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {n}{m}}\,}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {n}{m}}\,}</annotation>

</semantics>

</math><img src="./61c4896662a1dd9088c6dfcec40b6b17c1b00fe8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.666ex; height:3.009ex;" alt="{\displaystyle {\tfrac {n}{m}}\,}" loading="lazy"> be constant, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\,}</annotation>

</semantics>

</math><img src="./f08ce4d4c86c5b43f36c8435fb598da6471047c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.436ex; height:1.676ex;" alt="{\displaystyle r\,}" loading="lazy"> be the maximum degree of any vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\,}</annotation>

</semantics>

</math><img src="./293563891196765d2d51e0dd54e1ae1000ba9def.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.151ex; height:2.176ex;" alt="{\displaystyle R\,}" loading="lazy">. Note that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\,}</annotation>

</semantics>

</math><img src="./f08ce4d4c86c5b43f36c8435fb598da6471047c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.436ex; height:1.676ex;" alt="{\displaystyle r\,}" loading="lazy"> is also constant for known constructions.

<ol><li>Pre-processing: It takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mr)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mr)\,}</annotation>

</semantics>

</math><img src="./40d3aebf3734c86cca6a32b944f5ea4e3f5ee162.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.059ex; height:2.843ex;" alt="{\displaystyle O(mr)\,}" loading="lazy"> time to compute whether each vertex in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\,}</annotation>

</semantics>

</math><img src="./293563891196765d2d51e0dd54e1ae1000ba9def.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.151ex; height:2.176ex;" alt="{\displaystyle R\,}" loading="lazy"> has an odd or even number of neighbors.</li>

<li>Pre-processing 2: We take <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(dn)=O(dmr)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(dn)=O(dmr)\,}</annotation>

</semantics>

</math><img src="./03d129c2e601fa6b21f76841b947b80260497b05.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.566ex; height:2.843ex;" alt="{\displaystyle O(dn)=O(dmr)\,}" loading="lazy"> time to compute a list of vertices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}\,}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}\,}</annotation>

</semantics>

</math><img src="./e553751e245e05abb36ab6cff54f86b0037b759c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.314ex; height:2.009ex;" alt="{\displaystyle v_{i}\,}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L\,}</annotation>

</semantics>

</math><img src="./d330bc0cd693cc87e3943137dc591038a89f77e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.97ex; height:2.176ex;" alt="{\displaystyle L\,}" loading="lazy"> which have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o(i)>e(i)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o(i)>e(i)\,}</annotation>

</semantics>

</math><img src="./5a5074fcff782572239cabd11c746217440a20bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.92ex; height:2.843ex;" alt="{\displaystyle o(i)>e(i)\,}" loading="lazy">.</li>

<li>Each Iteration: We simply remove the first list element. To update the list of odd / even vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\,}</annotation>

</semantics>

</math><img src="./293563891196765d2d51e0dd54e1ae1000ba9def.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.151ex; height:2.176ex;" alt="{\displaystyle R\,}" loading="lazy">, we need only update <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(d)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(d)\,}</annotation>

</semantics>

</math><img src="./434b621b4d66e8bf15c727c228b437f2d6744e31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.186ex; height:2.843ex;" alt="{\displaystyle O(d)\,}" loading="lazy"> entries, inserting / removing as necessary. We then update <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(dr)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(dr)\,}</annotation>

</semantics>

</math><img src="./52d032fe43a1ef2a78bbfeb2e12c0073ce18b4ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.234ex; height:2.843ex;" alt="{\displaystyle O(dr)\,}" loading="lazy"> entries in the list of vertices in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L\,}</annotation>

</semantics>

</math><img src="./d330bc0cd693cc87e3943137dc591038a89f77e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.97ex; height:2.176ex;" alt="{\displaystyle L\,}" loading="lazy"> with more odd than even neighbors, inserting / removing as necessary. Thus each iteration takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(dr)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(dr)\,}</annotation>

</semantics>

</math><img src="./52d032fe43a1ef2a78bbfeb2e12c0073ce18b4ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.234ex; height:2.843ex;" alt="{\displaystyle O(dr)\,}" loading="lazy"> time.</li>

<li>As argued above, the total number of iterations is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\,}</annotation>

</semantics>

</math><img src="./37129e832c2c81b9f146dd22228d409bd099b295.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.427ex; height:1.676ex;" alt="{\displaystyle m\,}" loading="lazy">.</li></ol>

This gives a total runtime of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(mdr)=O(n)\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(mdr)=O(n)\,}</annotation>

</semantics>

</math><img src="./6cb0590e58b3d126fd34ed6054714f886689bd55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.35ex; height:2.843ex;" alt="{\displaystyle O(mdr)=O(n)\,}" loading="lazy"> time, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d\,}</annotation>

</semantics>

</math><img src="./0f203b686a923982358b9274fb508753ac31b996.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.603ex; height:2.176ex;" alt="{\displaystyle d\,}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\,}</annotation>

</semantics>

</math><img src="./f08ce4d4c86c5b43f36c8435fb598da6471047c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.436ex; height:1.676ex;" alt="{\displaystyle r\,}" loading="lazy"> are constants.

<ul><li><a href="Expander_graph" title="Expander graph">Expander graph</a></li>

<li><a href="Low-density_parity-check_code" title="Low-density parity-check code">Low-density parity-check code</a></li>

<li>Linear time encoding and decoding of error-correcting codes</li>

<li>ABNNR and AEL codes</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

This article is based on Dr. Venkatesan Guruswami's course notes.<a href="#cite_note-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSipserSpielman1996" class="citation journal cs1">Sipser, M.; Spielman, D.A. (1996). "Expander codes". IEEE Transactions on Information Theory. 42 (6): 1710–1722. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F18.556667">10.1109/18.556667</a>.</cite>

</li>

<li id="cite_note-lossless-2"><a href="#cite_ref-lossless_2-0">^</a> <cite id="CITEREFCapalboReingoldVadhanWigderson2002" class="citation book cs1">Capalbo, M.; Reingold, O.; Vadhan, S.; Wigderson, A. (2002). <a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=510003">"Randomness conductors and constant-degree lossless expanders"</a>. STOC '02 Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM. pp. 659–668. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F509907.510003">10.1145/509907.510003</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-58113-495-7</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1918841">1918841</a>.</cite>

</li>

<li id="cite_note-spielman-3"><a href="#cite_ref-spielman_3-0">^</a> <cite id="CITEREFSpielman1996" class="citation journal cs1">Spielman, D. (1996). "Linear-time encodable and decodable error-correcting codes". IEEE Transactions on Information Theory. 42 (6): 1723–31. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2736">10.1.1.47.2736</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F18.556668">10.1109/18.556668</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFGuruswami2006" class="citation web cs1">Guruswami, V. (15 November 2006). <a rel="nofollow" class="external text" href="http://www.cs.washington.edu/education/courses/cse533/06au/lecnotes/lecture13.pdf">"Lecture 13: Expander Codes"</a> (PDF). CSE 533: Error-Correcting. University of Washington.</cite>

<cite id="CITEREFGuruswami2010" class="citation web cs1">Guruswami, V. (March 2010). <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes8.pdf">"Notes 8: Expander Codes and their decoding"</a> (PDF). Introduction to Coding Theory. Carnegie Mellon University.</cite>

<cite id="CITEREFGuruswami2004" class="citation journal cs1">Guruswami, V. (September 2004). <a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=1027924">"Guest column: error-correcting codes and expander graphs"</a>. ACM SIGACT News. 35 (3): 25–41. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1027914.1027924">10.1145/1027914.1027924</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17550280">17550280</a>.</cite>

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-07-22" href="https://en.wikipedia.org/wiki/?title=Expander_code&oldid=1235978028">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>